`
https://leetcode.cn/problems/reconstruct-itinerary/
`

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
  // 构建邻接表图结构
  const graph = new Map()
  for (const [from, to] of tickets) {
    if (!graph.has(from)) {
      graph.set(from, [])
    }
    graph.get(from).push(to)
  }

  // 对每个节点的边字典序排序，确保最先遍历到字典序最小的节点，结果就是字典序最小的
  for (const tos of graph.values()) {
    tos.sort()
  }

  const postOrder = []

  // 遍历图，获取后序遍历结果
  function dfs(node) {
    // 处理没有出度的节点
    if (!graph.has(node)) {
      postOrder.push(node)
      return
    }
    const tos = graph.get(node)
    while (tos.length > 0) {
      // 拿到字典序最小的相连节点
      const v = tos.shift()
      dfs(v)
    }
    postOrder.push(node)
  }
  dfs("JFK")
  // 返回后序遍历的翻转，就是欧拉路径
  return postOrder.reverse()
};